﻿#include <iostream>
#include "BinaryTree.h"
#include <assert.h>
#include <vector>

using namespace std;

static void traverse(BinaryTreeNode* head, vector<BinaryTreeNode*>& vec)
{
	if (!head) return;

	traverse(head->left, vec);
	vec.push_back(head);
	traverse(head->right, vec);
}

static void findParent(BinaryTreeNode* head, BinaryTreeNode* child, BinaryTreeNode** parent)
{
	if (!head) return;

	findParent(head->left, child, parent);
	if (head->left == child)
	{
		*parent = head;
	}
	else if (head->right == child)
	{
		*parent = head;
	}

	findParent(head->left, child, parent);
}

static void changePositions(BinaryTreeNode* head, BinaryTreeNode* err0, BinaryTreeNode* err1)
{
	BinaryTreeNode* errParent0 = nullptr;
	BinaryTreeNode* errParent1 = nullptr;

	if (err0 == head)
	{
		if (err0->right == err1)
		{
			auto errLeft0 = err0->left;
			auto errLeft1 = err1->left;
			auto errRight1 = err1->right;
			err1->left = errLeft0;
			err1->right = err0;
			err0->left = errLeft1;
			err0->right = errRight1;
		}
		else
		{
			findParent(head, err1, &errParent1);
			auto errLeft0 = err0->left;
			auto errRight0 = err0->right;
			auto errLeft1 = err1->left;
			auto errRight1 = err1->right;

			if (errParent1->left == err1)
			{
				errParent1->left = err0;
			}
			else if (errParent1->right == err1)
			{
				errParent1->right = err0;
			}

			err1->left = errLeft0;
			err1->right = errRight0;
			err0->left = errLeft1;
			err0->right = errRight1;
		}
	}
	else if (err1 == head)
	{
		if (err1->left == err0)
		{
			auto errRight1 = err1->right;
			auto errLeft0 = err0->left;
			auto errRight0 = err0->right;
			err0->left = err1;
			err0->right = errRight1;
			err1->left = errLeft0;
			err1->right = errRight0;
		}
		else
		{
			findParent(head, err0, &errParent0);
			auto errLeft0 = err0->left;
			auto errRight0 = err0->right;
			auto errLeft1 = err1->left;
			auto errRight1 = err1->right;

			if (errParent0->left == err0)
			{
				errParent0->left = err1;
			}
			else if (errParent0->right == err0)
			{
				errParent0->right = err1;
			}

			err0->left = errLeft1;
			err0->right = errRight1;
			err1->left = errLeft0;
			err1->right = errRight0;
		}
	}
	else if (err0->right == err1)
	{
		findParent(head, err0, &errParent0);
		auto errLeft0 = err0->left;
		auto errLeft1 = err1->left;
		auto errRight1 = err1->right;
		if (errParent0->left == err0)
		{
			errParent0->left = err1;
		}
		else if (errParent0->right == err0)
		{
			errParent0->right = err1;
		}

		err1->left = errLeft0;
		err1->right = err0;
		err0->left = errLeft1;
		err0->right = errRight1;
	}
	else if (err1->left == err0)
	{
		findParent(head, err1, &errParent1);
		auto errRight1 = err1->right;
		auto errLeft0 = err0->left;
		auto errRight0 = err0->right;
		if (errParent1->left == err1)
		{
			errParent1->left = err0;
		}
		else if (errParent1->right == err1)
		{
			errParent1->right = err0;
		}

		err0->left = err1;
		err0->right = errRight1;
		err1->left = errLeft0;
		err1->right = errRight0;
	}
	else
	{
		findParent(head, err0, &errParent0);
		findParent(head, err1, &errParent1);

		auto errLeft0 = err0->left;
		auto errRight0 = err0->right;
		auto errLeft1 = err1->left;
		auto errRight1 = err1->right;

		if (errParent0 == errParent1)
		{
			if (errParent0->left == err0)
			{
				errParent0->left = err1;
				errParent0->right = err0;
			}
			else if (errParent0->right == err0)
			{
				errParent0->left = err0;
				errParent0->right = err1;
			}
		}
		else if (errParent0->left == err0 && errParent1->left == err1)
		{
			errParent0->left = err1;
			errParent1->left = err0;
		}
		else if (errParent0->left == err0 && errParent1->right == err1)
		{
			errParent0->left = err1;
			errParent1->right = err0;
		}
		else if (errParent0->right == err0 && errParent1->left == err1)
		{
			errParent0->right = err1;
			errParent1->left = err0;
		}
		else if (errParent0->right == err0 && errParent1->right == err1)
		{
			errParent0->right = err1;
			errParent1->right = err0;
		}

		err1->left = errLeft0;
		err1->right = errRight0;
		err0->left = errLeft1;
		err0->right = errRight1;
	}
}

static void correctTree(BinaryTreeNode* head)
{
	vector<BinaryTreeNode*> vec;
	traverse(head, vec);
	BinaryTreeNode* errs[2];
	errs[0] = nullptr;
	errs[1] = nullptr;

	int descOrderTimes = 0;
	int prev = -1;
	for (auto it = vec.begin(); it != vec.end(); it++)
	{
		if ((*it)->getValue() < prev)
		{
			++descOrderTimes;
		}

		prev = (*it)->getValue();
	}

	BinaryTreeNode* prevNode = nullptr;
	if (descOrderTimes == 1)
	{
		for (auto it = vec.begin(); it != vec.end(); it++)
		{
			if (prevNode && (*it)->getValue() < prevNode->getValue())
			{
				errs[0] = prevNode;
				errs[1] = *it;
				break;
			}

			prevNode = *it;
		}
	}
	else if (descOrderTimes == 2)
	{
		descOrderTimes = 0;
		for (auto it = vec.begin(); it != vec.end(); it++)
		{
			if (prevNode && (*it)->getValue() < prevNode->getValue())
			{
				++descOrderTimes;
				if (descOrderTimes == 1)
				{
					errs[0] = prevNode;
				}
				else
				{
					errs[1] = *it;
				}
			}

			prevNode = *it;
		}
	}
	else if (descOrderTimes > 2)
	{
		assert(false && "There are more than 2 error nodes.");
	}

	if (errs[0])
	{
		printf("1st error node:%d(%d)\n", errs[0]->getValue(), errs[0]->getId());
		printf("2nd error node:%d(%d)", errs[1]->getValue(), errs[1]->getId());
		changePositions(head, errs[0], errs[1]);
	}
	else
	{
		printf("error node not found.");
	}
}

/**
 * 一颗二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这颗二叉树不再试搜索二叉树，请找到这两个错误节点并返回。
 * 已知二叉树中所有节点的值都不一样，给定二叉树的头结点head，返回一个长度为2的二叉树节点类型的数组errs，errs[0]表示一个错误节点，errs[1]表示另一个错误节点。
 * 
 * 进阶：
 * 如果在原问题中得到了这两个错误节点，我们当然可以通过交换两个节点的节点值的方式让整棵二叉树重新成为搜索二叉树。
 * 但是现在要求你不能这么做，而是在结构上完全交换两个节点的位置，请实现调整的函数。
 * 
 * 思路：
 *                   4
 *                 /   \
 *                2     6
 *              /  \   /  \
 *             1    3 5    7
 * 
 * 中序遍历结果: 1->2->3->4->5->6->7
 * 遍历结果中，数字是递增的。
 * 但是，如果有2个错误节点，那就会破坏递增性:
 * 
 * 比如：
 *                   4
 *                 /   \
 *                5     6
 *              /  \   /  \
 *             1    3 2    7
 * 
 * 这颗错误的树的中序遍历结果是：1->5->3->4->2->6->7
 * 第一次发生降序的首节点是第一个错误节点，第二次发生降序的末节点是第二个错误节点。
 * 
 * 比如：
 *                   4
 *                 /   \
 *                3     6
 *              /  \   /  \
 *             1    2 5    7
 * 
 * 这颗错误的树的中序遍历结果是：1->3->2->4->5->6->7
 * 第一次发生降序的首节点是第一个错误节点，第一次发生降序的末节点是第二个错误节点。
 * 
 * 比如：
 *                   6
 *                 /   \
 *                2     4
 *              /  \   /  \
 *             1    3 5    7
 * 
 * 这颗错误的树的中序遍历结果是：1->2->3->6->5->4->7
 * 第一次发生降序的首节点是第一个错误节点，第二次发生降序的末节点是第二个错误节点。
 * 
 * 比如：
 *                   4
 *                 /   \
 *                2     5
 *              /  \   /  \
 *             1    3 6    7
 * 
 * 这颗错误的树的中序遍历结果是：1->2->3->4->6->5->7
 * 第一次发生降序的首节点是第一个错误节点，第一次发生降序的末节点是第二个错误节点。
 * 
 * 
 * 调换顺序注意事项：
 * 1. errs[0]和errs[1]是否有可能其中一个是整棵树的根节点?
 * 2. errs[0]和errs[1]是否相邻？哪个是父节点?
 * 3. errs[0]和errs[1]都有自己的父节点，它们分别是各自父节点的左孩子还是右孩子?
 * 
 * 对于第2条，由于errs[0]先被发现，故
 *                        errs[0]
 *                        /
 *                     errs[1]
 * 这个结构不可能出现；
 *                        errs[1]
 *                            \
 *                            errs[0]
 * 这个结构也不可能出现。
 * 
 */      
int main_twoWrongNodes()
{
	BinaryTreeNode* head = new BinaryTreeNode(0, 4);
	head->left = new BinaryTreeNode(1, 5);
	head->right = new BinaryTreeNode(2, 6);
	head->left->left = new BinaryTreeNode(3, 1);
	head->left->right = new BinaryTreeNode(4, 3);
	head->right->left = new BinaryTreeNode(5, 2);
	head->right->right = new BinaryTreeNode(6, 7);

	correctTree(head);

	deleteBinaryTree(head);
	return 0;
}